package com.leet.code.lcof;


/**
 * 剑指 Offer 04. 二维数组中的查找
 * 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 * <p>
 * <p>
 * <p>
 * 示例:
 * <p>
 * 现有矩阵 matrix 如下：
 * <p>
 * [
 * [1,   4,  7, 11, 15],
 * [2,   5,  8, 12, 19],
 * [3,   6,  9, 16, 22],
 * [10, 13, 14, 17, 24],
 * [18, 21, 23, 26, 30]
 * ]
 * 给定 target = 5，返回 true。
 * <p>
 * 给定 target = 20，返回 false。
 * <p>
 * <p>
 * <p>
 * 限制：
 * <p>
 * 0 <= n <= 1000
 * <p>
 * 0 <= m <= 1000
 */
public class Code04 {
    public static void main(String[] args) {
        int[][] matrix =
                {
                        {1, 4, 7, 11, 15},
                        {2, 5, 8, 12, 19},
                        {3, 6, 9, 16, 22},
                        {10, 13, 14, 17, 24},
                        {18, 21, 23, 26, 30}
                };

        System.out.println(findNumberIn2DArray(matrix, 5));
    }

    static boolean findNumberIn2DArray(int[][] matrix, int target) {

        //如果数组空的直接false
        if (matrix.length == 0) {
            return false;
        }
        if (matrix[0].length == 0) {
            return false;
        }

        //先判断数组第一个数
        if (matrix[0][0] >= target) {
            return matrix[0][0] == target;
        }

        int xEnd = matrix[0].length - 1;
        int yEnd = matrix.length - 1;

        //判断数组最大大数
        if (matrix[yEnd][xEnd] <= target) {
            return matrix[yEnd][xEnd] == target;
        }


        int xStart = 0, yStart = 0, xMiddle = 0, yMiddle = 0, xs = xStart, ys = yStart;


        while (true) {

            while (xStart <= xEnd) {
                xMiddle = (xStart + xEnd) >>> 1;
                if (matrix[ys][xMiddle] == target) {
                    return true;
                }
                if (matrix[ys][xMiddle] < target) {
                    xStart = xMiddle + 1;
                } else {
                    xEnd = xMiddle - 1;
                }
            }
            xEnd = xMiddle;
            ys++;
            xStart = xs;

            if (ys > yEnd) {
                return false;
            }

            while (yStart <= yEnd) {
                yMiddle = (yStart + yEnd) >>> 1;
                if (matrix[yMiddle][xs] == target) {
                    return true;
                }
                if (matrix[yMiddle][xs] < target) {
                    yStart = yMiddle + 1;
                } else {
                    yEnd = yMiddle - 1;
                }

            }

            yEnd = yMiddle;
            xs++;
            yStart = ys;

            if (xs > xEnd) {
                return false;
            }

        }


    }


}
